#include<iostream>
#include<string.h>
#include<fstream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
using namespace std;


//Maxsize: 最大顶点数
#define MaxSize  100
#define INF 32767

//景点信息
struct verType{
    char info[512]; //景点介绍
    char name[MaxSize]; //景点名字
};
//地图
struct Graph
{
    verType vexs[MaxSize];// 存放顶点
    int arcs[MaxSize][MaxSize];// 邻接矩阵
    int vertexNum,arcNum;// 顶点数和边数
};


void printInfo(Graph &G);
int LocateVex(Graph G, char name[]);
void InitMap(Graph &G);
void AskDirection(Graph &G);
void Dijkstra(Graph &G,int v,int path[]);

void AddVex(Graph &G);
void DeleteVex(Graph &G);
void ChangeVex(Graph &G);
void SearchVex(Graph &G);

void setPath(Graph &G,int i,int j,int w);
void AddPath(Graph &G);

void WriteMap(Graph G); 



int main(){
	Graph G;	
	//初始化图，并从文件中读取信息 
	InitMap(G);

	char choice;	
	while(1){
		system("cls");
		cout<<"**************欢迎来到四川轻化工大学******************"<<endl;
		cout<<"1.查询景点信息"<<endl;
		cout<<"2.问路查询"<<endl;
		cout<<"3.修改一个已有景点的相关信息"<<endl;
		cout<<"4.增加一个新景点及其相关信息"<<endl;
		cout<<"5.删除一个景点及其相关信息"<<endl;
		cout<<"6.增加一条新的路径"<<endl;
//		cout<<"7.删除一条路径"<<endl;
//		cout<<"-1.退出"<<endl;
		cout<<"**************四川轻化工大学校园导航系统******************"<<endl;
		cout<<"请选择需要的服务："<<endl;
				
		cin>>choice;
		
		//检测非法输入 
		char a=getchar();
		if(a!='\n'){
			cout<<"输入错误！\n按下任意键继续....\n";
			system("cls");
			continue;
		} 
		system("cls");
		printInfo(G);
		switch(choice){
			case '1':
				SearchVex(G);
				break;
			case '2':
				AskDirection(G);	 
				break;
			case '3':
				ChangeVex(G);
				break;
			case '4':
				AddVex(G);
				break;
			case'5':
				DeleteVex(G);
				break;
			case'6':
				AddPath(G);
				break;
//			case'7':
//				DeletePath(G);
//				break;
//			case'-1':
//				exit(1);
			default:
				cout<<"输入错误！\n请重新输入！";
				getchar();

				break;
		}
	}	
    return 0;
}



void WriteMap(Graph G) {
    ofstream out("map.txt");

    out << G.vertexNum << "\t" << G.arcNum << endl;

    // 写入顶点信息
    for (int i = 0; i < G.vertexNum; i++) {
        out << G.vexs[i].name << "\t" << G.vexs[i].info << endl;
    }

    // 写入边的信息
    for (int i = 0; i < G.vertexNum; i++) {
        for (int j = i + 1; j < G.vertexNum; j++) {
            if (G.arcs[i][j] != INF && G.arcs[i][j] !=0) {
                out << G.vexs[i].name << "\t";
                out << G.vexs[j].name << "\t";
                out << G.arcs[i][j] << endl;

            }
        }
    }
    out.close();
}



//增
void AddVex(Graph &G){	
    if (G.vertexNum == MaxSize) {
        cout<<"已达到最大顶点数，无法添加新的景点。"<<endl;
    }
	else{	
	    cout<<"请输入新景点的信息"<<endl<<"景点名字：";
	    cin.getline(G.vexs[G.vertexNum].name, MaxSize);
	    cout<<"景点介绍：";
	    cin.getline(G.vexs[G.vertexNum].info, 512);
	    
	    printInfo(G);
		int n=0,flag=0;
	    while(flag!=-1){//输入-1就结束 	    
		    cout<<"该景点与哪一个景点之间有路径（输入景点序号）：";
		    int index; 
		    cin>>index;
		    if(index==-1) break;
		    
		    cout<<"与"<<G.vexs[index-1].name<<"的距离为：";
			int distance;
			cin>>distance;
			setPath(G,G.vertexNum,index-1,distance);
			n++;			
		    cout<<"与该景点之间的路径已经添加成功！\n（1继续添加路径/-1结束）\n" ;
			cin>>flag;
		}
	    
	    G.vertexNum++; 
	    G.arcNum+=n;
		
//	    WriteMap(G);
	    cout<<"添加成功！按任意键返回主菜单..."<<endl;
	    getch();
	}
}

//删
void DeleteVex(Graph &G){
	while(1){
		int v;
		cout<<"请输入要删除的景点序号(输入-1返回)";
		cin>>v; 
		if(v==-1){
			system("cls"); 
			return;
		}
		 
		int i,j;
		for(i=0;i<G.vertexNum;i++)
			if(G.arcs[v][i]!=INF){	
				setPath(G,v,i,INF);
				G.arcNum=G.arcNum-2;
			}
		for(i=v+1;i<G.vertexNum;i++)//行 
			for(j=0;j<G.vertexNum;j++)//列 
				G.arcs[i-1][j]=G.arcs[i][j];	
		for(i=v+1;i<G.vertexNum;i++)//列 
			for(j=0;j<G.vertexNum-1;j++)//行 
				G.arcs[j][i-1]=G.arcs[j][i];
		for(i=v+1;i<G.vertexNum;i++)
			G.vexs[i-1]=G.vexs[i];
		G.vertexNum--;
		
	}
//	WriteMap(G);
}

//改
void ChangeVex(Graph &G){
			
	cout<<"请输入要修改的景点序号（输入-1返回）"<<endl;		
    int index;
    cin>>index;
	    
    if(index==-1){
    	system("cls");
	}
	else if (index < 0 || index >= G.vertexNum) {
        cout<<"未找到该景点！按任意键以重新输入..."<<endl;
        getch();
        system("cls");
        printInfo(G);
        ChangeVex(G);
    }
	else{
		cin.ignore();
		cout<<"请输入该景点的新信息"<<endl<<"景点名字：";
    	cin.getline(G.vexs[index-1].name, MaxSize);
		cout<<"景点介绍：";
    	cin.getline(G.vexs[index-1].info, 512);
    	
    	cout<<"是否更改与之相关的路径（1是/-1否）" <<endl;
    	int f=0;
    	cin>>f;
    	if(f==1){		
			for(int i=0;i<G.vertexNum;i++){
				if(G.arcs[index-1][i]!=INF){
					cout<<"该景点到"<<G.vexs[i].name<<"的距离改为：";
					int distance;
		    		cin>>distance;	
					setPath(G,index-1,i,distance);    		
				}	    	 
	    	}
    	}
    	else if(f==-1){
//	    	WriteMap(G);
	    	cout<<"修改成功!按任意键返回主菜单..."<<endl;
			getch();
		}
	}	
}

//查
void SearchVex(Graph &G){
	cout<<"请输入你想查询的景点：(1-8,输入-1返回)"<<endl;
	int choice;
	while(choice!=-1){
		cin>>choice;
		cout<<"景点："<<G.vexs[choice-1].name<<endl;
		cout<<"介绍："<<G.vexs[choice-1].info<<endl;
	}
	system("cls");
	return;
} 



void setPath(Graph &G,int i,int j,int w){
	G.arcs[i][j]=w;
	G.arcs[j][i]=w;
}

//增 
void AddPath(Graph &G){
	int v1=0,v2=0,w=0;
	while(true){
		cout<<"（输入-1返回）"<<endl;
		cout<<"请输入起点序号:";
		cin>>v1;
		if(v1==-1 || v2==-1 || w==-1){
			system("cls"); 
			return;
		}
		cout<<"请输入终点序号:";
		cin>>v2;
		if(v1==-1 || v2==-1 || w==-1){
			system("cls"); 
			return;
		}
		cout<<"请输入两地的距离:";
		cin>>w;
		if(v1==-1 || v2==-1 || w==-1){
			system("cls"); 
			return;
		}
		else{
			if(G.arcs[v1][v2]!=INF){
				cout<<G.vexs[v1].name<<"和"<<G.vexs[v2].name<<"这两个景点之间已经存在路径，不需要在添加路径！"<<endl;
				return;
			}
			G.arcNum++;
//			G.arcs[v1][v2]=w;
//			G.arcs[v2][v1]=w;
			setPath(G,v1,v2,w);
			cout<<"成功在"<<G.vexs[v1].name<<"和"<<G.vexs[v2].name<<"这两个景点之间添加一条长度为"<<w<<"的路径"<<endl;
		} 
	}
//	WriteMap(G);
}

//删
void DeletePath(Graph &G){
	;
}